package com.zj.leetcode.medium.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: algorithm
 * @description: N 叉树的层序遍历
 * 429 n-ary-tree-level-order-traversal
 * @author: Zhang Bo
 * @create: 2022-06-09 13:48:49
 **/
public class NAryTreeLevelOrderTraversal {
    public static void main(String[] args) {
        Solution solution = new NAryTreeLevelOrderTraversal().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }


    class Solution {
        public List<List<Integer>> levelOrder(Node root) {
            List<List<Integer>> ans = new ArrayList<>();
            if(root == null) return ans;
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            while(!queue.isEmpty()) {
                int size = queue.size();
                List<Integer> res = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    Node node = queue.poll();
                    if(node.children != null) {
                        queue.addAll(node.children);
                    }
                    res.add(node.val);
                }
                ans.add(res);
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}